/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package lib.random;

import java.util.ArrayList;
import java.util.Collections;
import lib.datatypes.Edge;
import lib.datatypes.TwoDimensionalLongPoint;

/**
 * Generates random graphs.
 * 
 * @author dolphinigle
 */
public class RandomGraph {

  /**
   * Random source
   */
  protected ExtendedRandom random_;

  /**
   * Constructs a random graph generator
   * @param random base random seed source
   */
  public RandomGraph(ExtendedRandom random) {
    random_ = random;
  }

  /**
   * Generates a random and symmetric adjacency matrix
   * @param nodes number of nodes in the graph
   * @param edges number of edges in the graph
   * @param must_be_connected true iff the graph must be connected
   * @return a nodesxnodes array of boolean, j-th element of i-th element of
   * which is true iff there is a path from node i to j. i-th element of the
   * i-th element of which will be false.
   */
  public boolean[][] randomSymmetricAdjacencyMatrix(int nodes, int edges,
          boolean must_be_connected) {
    boolean[][] adjm = new boolean[nodes][nodes];

    assert (edges <= nodes * (nodes-1) / 2);

    ArrayList<Integer> nodes_list = new ArrayList<Integer>();
    for (int i = 0; i < nodes; ++i) {
      nodes_list.add(i);
    }

    if (must_be_connected) {
      assert edges > nodes-1;

      Collections.shuffle(nodes_list, random_);

      for (int i = 1; i < nodes; ++i) {
        int partner = nodes_list.get(random_.nextInt(i));
        adjm[nodes_list.get(i)][partner] = true;
        adjm[partner][nodes_list.get(i)] = true;
        --edges;
      }

    }

    ArrayList<Edge> edges_list = new ArrayList<Edge>();

    for (int i = 0; i < nodes; ++i) for (int j = i+1; j < nodes; ++j) {
      if (!adjm[i][j]) edges_list.add(new Edge(i, j));
    }

    Collections.shuffle(edges_list, random_);

    for (int i = 0; i < edges; ++i) {
      adjm[edges_list.get(i).getSource()][edges_list.get(i).getDestination()] =
              true;
      adjm[edges_list.get(i).getDestination()][edges_list.get(i).getSource()] =
              true;
    }

    return adjm;

  }

  /**
   * Generates a random path on an undirected graph
   * <br/><br/>
   * A path is a graph with exactly N nodes and N-1 edges such that the degree
   * of each node is either 2 or 1.
   * @param nodes the number of nodes in the path
   * @param origin node that the start of the path. 0-based indexed
   * @param end node that the end of the path. 0-based indexed. Note that
   * since the graph is undirected, origin and end are equivalent
   * @return the adjacency matrix of the graph
   */
  public boolean[][] randomPathSymmetricAdjacencyMatrix(int nodes,
          int origin, int end) {

    assert origin >= 0 && origin < nodes;
    assert end >= 0 && end < nodes;

    boolean[][] adj = new boolean[nodes][nodes];

    ArrayList<Integer> intermedianodes = new ArrayList<Integer>();

    for (int i = 0; i < nodes; ++i) {
      if (i == origin || i == end) continue;
      intermedianodes.add(i);
    }

    Collections.shuffle(intermedianodes, random_);

    adj[origin][intermedianodes.get(0)] = adj[intermedianodes.get(0)][origin] =
            true;
    adj[intermedianodes.get(nodes-3)][end] =
            adj[end][intermedianodes.get(nodes-3)] =
            true;

    for (int i = 0; i < intermedianodes.size() - 1; ++i) {
      adj[intermedianodes.get(i)][intermedianodes.get(i+1)] =
              adj[intermedianodes.get(i+1)][intermedianodes.get(i)] =
              true;
    }

    return adj;

  }

  /**
   * Generates a random and symmetric positive weighted adjacency matrix. The weights
   * will be based on euclidian distance in a 2d grid.
   * @param nodes number of nodes in the graph
   * @param edges number of edges in the graph
   * @param must_be_connected true iff the graph must be connected
   * @param upper_bound maximum cost of each weight of the edges in the graph
   * minimum cost is 1
   * @return a nodes x nodes array of long. The j-th element of the i-th element
   * of which will be :
   * <ul>
   * <li>a long 1 and upper_bound indicates an edge with weight
   * equal to that</li>
   * <li>-1L if no edge</li>
   * </ul>
   */
  public long[][] randomEuclidianBasedWeightedSymmetricAdjacencyMatrixLong(
          int nodes,
          int edges,
          boolean must_be_connected,
          long upper_bound) {
    long[][] adj = new long[nodes][nodes];

    for (int i = 0; i < nodes; ++i) for (int j = 0; j < nodes; ++j)
      adj[i][j] = -1L;

    assert (edges <= nodes * (nodes-1) / 2);

    RandomPoints random_points = new RandomPoints(random_);

    // generate random grid

    long limit = Math.round((double)upper_bound / Math.sqrt(2.0)) - 1L;
    TwoDimensionalLongPoint[] points = random_points.
            GenerateDistinctTwoDimensionalLongPoints(nodes, 0,
            limit);

    boolean[][] adjexists = this.
            randomSymmetricAdjacencyMatrix(nodes, edges, must_be_connected);

    for (int i = 0; i < nodes; ++i) for (int j = i+1; j < nodes; ++j) {
      if (adjexists[i][j]) {
        adj[i][j] = adj[j][i] = Math.round(Math.hypot(
                (double)points[i].x() - (double)points[j].x(),
                (double)points[i].y() - (double)points[j].y()));
      }
    }
    return  adj;

  }

}
